package com.zh.note.leetcode.tree;

import com.zh.note.leetcode.model.TreeNode;

import java.util.*;

/**
 * 二叉树的遍历
 */
public class TreeTraversal {

    /**
     * 先序遍历(递归法)
     */
    public void preorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        res.add(root.val);
        preorder(root.left, res);
        preorder(root.right, res);
    }

    /**
     * 中序遍历(递归法)
     */
    public void inorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }

    /**
     * 后序遍历(递归法)
     */
    public void postorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        postorder(root.left, res);
        postorder(root.right, res);
        res.add(root.val);
    }

    /**
     * 先序遍历（迭代法）
     * 中-左-右，入栈顺序：中-右-左
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            res.add(node.val);//中
            if (node.right != null) {
                stack.push(node.right);//右
            }
            if (node.left != null) {
                stack.push(node.left);//左
            }
        }
        return res;

    }

    /**
     * 后序遍历（迭代法）
     * 后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果
     */
    public List<Integer> postorderTraversal(TreeNode root) {

        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            res.add(node.val);//中
            if (node.left != null) {
                stack.push(node.left);//左
            }
            if (node.right != null) {
                stack.push(node.right);//右
            }
        }
        // 翻转
        Collections.reverse(res);
        return res;

    }

    /**
     * 中序遍历（迭代法）
     */
    public List<Integer> inorderTraversal(TreeNode root) {

        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        // 定义一个指针,记录访问过的元素
        TreeNode cur = root;
        //指针不为空，或者栈不为空
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                res.add(cur.val);
                cur = cur.right;
            }
        }
        return res;

    }


    /**
     * 102. 二叉树的层序遍历
     *
     * @param root
     * @return
     */
    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        if (root != null) {
            queue.add(root);
        }
        while (!queue.isEmpty()) {
            // 记录当前层节点数量
            int n = queue.size();
            // 用来存储某一层节点
            List<Integer> level = new ArrayList<>();
            // 遍历每一层
            for (int i = 0; i < n; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            res.add(level);
        }
        return res;
    }


    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode();
        treeNode.val = 1;
        TreeNode left = new TreeNode(2);
        TreeNode right = new TreeNode(3);
        treeNode.left = left;
        treeNode.right = right;
        TreeNode four = new TreeNode(4);
        TreeNode five = new TreeNode(5);
        TreeNode six = new TreeNode(6);
        TreeNode seven = new TreeNode(7);
        treeNode.left.left = four;
        treeNode.left.right = five;
        treeNode.right.left = six;
        treeNode.right.right = seven;
        levelOrder(treeNode);
    }
}
